%%
%% Copyright 2007, 2008, 2009 Elsevier Ltd
%%
%% This file is part of the 'Elsarticle Bundle'.
%% ---------------------------------------------
%%
%% It may be distributed under the conditions of the LaTeX Project Public
%% License, either version 1.2 of this license or (at your option) any
%% later version.  The latest version of this license is in
%%    http://www.latex-project.org/lppl.txt
%% and version 1.2 or later is part of all distributions of LaTeX
%% version 1999/12/01 or later.
%%
%% The list of all files belonging to the 'Elsarticle Bundle' is
%% given in the file `manifest.txt'.
%%

%% Template article for Elsevier's document class `elsarticle'
%% with harvard style bibliographic references
%% SP 2008/03/01
%%
%%
%%
%% $Id: elsarticle-template-harv.tex 4 2009-10-24 08:22:58Z rishi $
%%
%%
%% \documentclass[preprint,authoryear,12pt]{elsarticle}

%% Use the option review to obtain double line spacing
%% \documentclass[authoryear,preprint,review,12pt]{elsarticle}

%% Use the options 1p,twocolumn; 3p; 3p,twocolumn; 5p; or 5p,twocolumn
%% for a journal layout:
%% \documentclass[final,authoryear,1p,times]{elsarticle}
%% \documentclass[final,authoryear,1p,times,twocolumn]{elsarticle}
%% \documentclass[final,authoryear,3p,times]{elsarticle}
\documentclass[final,authoryear,3p,times,twocolumn]{elsarticle}
%% \documentclass[final,authoryear,5p,times]{elsarticle}
%% \documentclass[final,authoryear,5p,times,twocolumn]{elsarticle}

%% if you use PostScript figures in your article
%% use the graphics package for simple commands
%% \usepackage{graphics}
%% or use the graphicx package for more complicated commands
%% \usepackage{graphicx}
%% or use the epsfig package if you prefer to use the old commands
%% \usepackage{epsfig}

%% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
\usepackage{color}
%% The amsthm package provides extended theorem environments
%% \usepackage{amsthm}

%% The lineno packages adds line numbers. Start line numbering with
%% \begin{linenumbers}, end it with \end{linenumbers}. Or switch it on
%% for the whole article with \linenumbers after \end{frontmatter}.
%% \usepackage{lineno}

%% natbib.sty is loaded by default. However, natbib options can be
%% provided with \biboptions{...} command. Following options are
%% valid:

%%   round  -  round parentheses are used (default)
%%   square -  square brackets are used   [option]
%%   curly  -  curly braces are used      {option}
%%   angle  -  angle brackets are used    <option>
%%   semicolon  -  multiple citations separated by semi-colon (default)
%%   colon  - same as semicolon, an earlier confusion
%%   comma  -  separated by comma
%%   authoryear - selects author-year citations (default)
%%   numbers-  selects numerical citations
%%   super  -  numerical citations as superscripts
%%   sort   -  sorts multiple citations according to order in ref. list
%%   sort&compress   -  like sort, but also compresses numerical citations
%%   compress - compresses without sorting
%%   longnamesfirst  -  makes first citation full author list
%%
%% \biboptions{longnamesfirst,comma}

% \biboptions{}

%% for debugging, please use the following declarations
\newcommand{\chg}[1]{\textcolor{red}{#1}}
\newcommand{\cmt}[1]{\textit{\textcolor{blue}{[#1]}}}
\newcommand{\desc}[1]{#1}

%% for release, please use the following ones
% \newcommand{\chg}[1]{#1}
% \newcommand{\cmt}[1]{}
% \newcommand{\desc}[1]{}

\journal{Geoxiom Project Reference}

\begin{document}

\begin{frontmatter}

%% Title, authors and addresses

%% use the tnoteref command within \title for footnotes;
%% use the tnotetext command for the associated footnote;
%% use the fnref command within \author or \address for footnotes;
%% use the fntext command for the associated footnote;
%% use the corref command within \author for corresponding author footnotes;
%% use the cortext command for the associated footnote;
%% use the ead command for the email address,
%% and the form \ead[url] for the home page:
%%
%% \title{Title\tnoteref{label1}}
%% \tnotetext[label1]{}
%% \author{Name\corref{cor1}\fnref{label2}}
%% \ead{email address}
%% \ead[url]{home page}
%% \fntext[label2]{}
%% \cortext[cor1]{}
%% \address{Address\fnref{label3}}
%% \fntext[label3]{}

\title{Geoxiom, a semantic-based geometric modeling technique with natural language}

%% use optional labels to link authors explicitly to addresses:
%% \author[label1,label2]{<author name>}
%% \address[label1]{<address>}
%% \address[label2]{<address>}

\author[thss]{Kan-Le Shi}

\address[thss]{School of Software, Tsinghua University, Beijing 100084, P. R. China}

\begin{abstract}

    Geoxiom is a quasi-natural language and the corresponding compiler of professional
        geometric-chart construction.
    It generates vector-based charts of geometric elements used in industrial
        publication field, such as paper writing and book documentation
    The geometric chart is completely generated by quasi-natural language,
        describing the shape definitions and their relations (constraints).
    No coordinates should be specified.
    It is the main difference between Geoxiom and other modeling or drawing languages.
    This manuscript introduces the background, the main framework, algorithms
        and architecture of the compiler of Geoxiom.

\end{abstract}

\begin{keyword}

    geoxiom \sep
    geometry \sep
    quasi-natural language \sep
    compiler \sep
    architecture

\end{keyword}

\end{frontmatter}

% \linenumbers

%% main text
\section{Introduction}

    Geoxiom is a quasi-natural language and the corresponding compiler of professional
        geometric-chart construction.
    It generates vector-based charts of geometric elements used in industrial publication
        field, such as paper writing and book documentation.
    The scripting language is quasi-natural, meaning that it is similar to natural
        descriptive languages of geometric objects in mathematics.

    Natural language processing is the first step of compiling.
    The processor matches the input script with prescribed patterns like an artificial
        intelligence agent (for example, ALICE). After understanding the input natural
        language, the input is converted into a list of constrains and definitions.
    A solver, which is based on constrained optimization, is used to compute all the
        unfixed points and attributes of geometric elements. And finally, an optimizer
        is used to adjust shape, position of labels and other detailed
        elements of the chart.
    The chart is output as vector-based objects, which can be converted into EPS or
        other vector-image formats.

    The geometric chart is completely generated by quasi-natural language, describing
        shape definitions and their relations (constraints).
    No coordinates should be specified.
    It is the main difference between Geoxiom and other modeling/drawing languages such
        as EPS.
    Since all the geometric charts in professional text books or papers illustrate
        principles or relations of geometric objects, it must can be described by natural
        languages.
    The point of view is proved by the descriptive caption/text below figures of papers
        in majority.
    So Geoxiom gives a way that paper writers only need to declare a chart once
        and it generates both the chart and the corresponding description.

\section{Architecture}

    \begin{figure}[ht]
        \label{fig:process}
        \centering
            \includegraphics[width=7cm]{process.eps}
        \caption{The main pipelining of script processing}
    \end{figure}
    Shown in Figure \ref{fig:process}, the main pipeline of the script processing
        can be cut into several steps.
    \begin{enumerate}
        \item \emph{Lexical analysis}\\
            The input Geoxiom script is first segmented into a stream of lexical objects.
            There are different types of lexical objects, also called \emph{elements},
                including \emph{keywords}, \emph{identifiers}, \emph{immediates} and
                \emph{symbols}.
            Any formats, such as returning or indents are lost after this step.
        \item \emph{Pattern matching and natural language processing}\\
            We use multi-level patterns to define the structure of the script, which
                are \emph{word}, \emph{phrase}, \emph{clause} and \emph{sentence}.
            The prescribed patterns give the pair of stream pattern and its
                meaning mapping rule.
            Then, the engine tries to optimize the matching over these patterns.
            Once the matching action completes, all the unknown elements in the pattern
                templates are decided and the whole structure forest
                can be constructed.
            Thus, we can output the required geometric objects, with some properties
                or attributes not fixed, and their constraints.
        \item \emph{Solving geometric objects using energy-minimization and constrained-optimization method}\\
            After the previous step, only geometric objects and their constraints are constructed.
            But their properties, such as their scales and positions, are not fixed.
            In this step, we solve these parameters using energy-minimization and
                constrained-optimization method, since it adapts for conflicts or missing
                constraints.
        \item \emph{Enhancement and labeling}\\
            The geometric constraints never specify the gesture of the chart.
            The solutions are multiple since any rotation transformation works.
            We first choose a best one and after that, we put on all
                labels, such as names of objects.
        \item \emph{Formatting and outputting}\\
            Finally, all internal geometric objects are converted to existing formats, such
                as EPS.

    \end{enumerate}

\subsection{Lexical analysis}

    First, \emph{lexical elements} are declared as follows.
    \begin{enumerate}
        \item \emph{Keywords}\\
            \emph{Keywords} are grammar-concerning words specified by pattern rules.
            Unlike other programming languages, keywords in Geoxiom lexical processor
                are much more, and they are not used to introduce a grammar block, such as
                \emph{if} or \emph{for}.
            They are only possible invariable words in pattern matching.
            Users have to note that the name of a geometric object cannot be a keyword,
                which is similar with other programming languages.
        \item \emph{Identifiers}\\
            A words that may be a name of an geometric object is called an \emph{identifier},
                which starts with a non-digit nor a symbol.
            For example, `A', `B', `O' are legal identifiers.
            And an identifier supports subscripts as its postfix.
            For example, `A\_1' denotes $A_1$, which preserves the grammar of \LaTeX.
        \item \emph{Immediate numbers}\\
            Numbers, in 8, 10 or 16 radices are acceptable.
            There are only two types of numbers, integer and real.
        \item \emph{Symbols}\\
            Symbols help to express special meanings.
            For example, the period dot ends one statement.
    \end{enumerate}

\subsection{Pattern matching and natural language processing}

    This is one of the most important steps in processing.
    First, we introduce a concept -- \emph{pattern}.
    A pattern is a pair of a template and a extraction rule.
    The template is a pre-compiled stream of lexical elements, with
        some wildcard symbols.
    For example, \\
        `$<$num:immediate$>$ circle $[$named $<$name:identifier$>$$]$'\\
        is a pattern expression.
    Symbol pair `$<$' and `$>$' denotes wildcard components, with their
        names and types appearing on two hands of the semicolon, respectively.
    Symbol pair `$[$' and `$]$' denotes optional parts.
    The internal extraction rules extract the value of wildcard and
        construct geometric objects and constraints.

    The input of the algorithm is the stream of lexical elements after the lexical
        analysis step.
    And we also provide a pattern library, which is a collection of patterns
        pre-compiled in our processing system.
    The algorithm will optimize the matching process, which tries to
        match patterns from the input stream as more as it can.
    Here we can give a short example for this.

    Assume that there are following patterns.
    \begin{enumerate}
        \item \emph{define $<$sth:phrase$>$}
        \item \emph{$<$num:immediate$>$ circle $[$named $<$name: identifier $>$$]$}
        \item \emph{$<$sth0:phrase$>$ $[$and $<$sth1:phrase$>$$]$}
    \end{enumerate}
    And if the specified lexical stream is,\\
    \emph{`define a circle O and another circle named P.'}
    The matching result might be
    \begin{enumerate}
        \item Rule 1: define \{a circle O and another circle named P.\}
        \item Rule 3: \{a circle O\} and \{another circle named P\}
        \item Rule 2: \{a\} circle \{O\}
        \item Rule 2: \{another\} circle named \{P\}
    \end{enumerate}
    So we can construct two definitions of circles such that
    \begin{enumerate}
        \item Circle \#1, Center \{O\}
        \item Circle \#2, Center \{P\}
    \end{enumerate}

    For the output of this step, we should find a algebraic method, which can enumerate
        all constraints completely.

\subsection{Solving geometric objects using energy-minimization and constrained-optimization method}

    All properties of geometric objects are first generated randomly, which is called the
        \emph{randomization} step.
    Then weak constraints are added to adjust their positions natural.
    For example, if there is a rectangle, the weak constraints first forms it as a square.
    And if there is a triangle, its default gesture is equilateral.
    Then, constraints are applied.
    For each step, we compute the Euclidean distance between the current model to the expected one,
        which can be illustrated by constraints.
    And then iterate bit-movement to achieve smaller Euclidean distance, until error criterions are
        all satisfied or timeout.

\subsection{Enhancement and labeling}

    This step computes the main directional vector of the chart first, and then adjust it to be
        horizontal.
    Then, add the labels in space.


fig:process\section{Algorithms and implementation}

\subsection{Geometric objects}

    \emph{Implicit attributes} are the clean attributes for storage
        and internal model representation, while \emph{explicit
        attributes} are properties that external objects could see.
        They are different.
    For example, a line stores the two end-points.
    These are implicit attributes.
    Besides them, the explicit attributes contains the properties such as middle-point.
    We should not store the middle-point, but the external objects could see.

    We should provide a transition-matrix in humongous space to represent their relations.
    For example, the two end-points of a line are $A$ and $B$, which are two-dimensional vectors.
    Then the middle-point is a combination of the transformed variables.
    That is,
    \begin{equation}
        \rm{middle\_point} ::= M_A A + M_B B
    \end{equation}
    Whether all attributes should be in humongous form is not decided.
    But this mechanism makes it possible to compute implicit attributes from explicit attributes.
    It can be decided after all attributes are listed.

    \begin{enumerate}
        \item \emph{Point}\\
            Implicit attributes: position:vector2d;\\
            Explicit attributes: position:vector2d.
        \item \emph{Circle}\\
            Implicit attributes: center:vector2d, radius:real;\\
            Explicit attributes: center:vector2d, radius:real.
        \item \emph{Ray}\\
            Implicit attributes: origin:vector2d, direction:vector2d;\\
            Explicit attributes: origin:vector2d, direction:vector2d; any-point:vector2d;\\
        \item \emph{Line}\\
            Implicit attributes: end-points:vector2d[2]; \\
            Explicit attributes: end-points:vector2d[2], middle-point:vector2d, $\lambda$-point:vector2d;

    \end{enumerate}


\section{Outstanding issues}

\section{Conclusion}


%% The Appendices part is started with the command \appendix;
%% appendix sections are then done as normal sections
%% \appendix

%% \section{}
%% \label{}

%% References
%%
%% Following citation commands can be used in the body text:
%%
%%  \citet{key}  ==>>  Jones et al. (1990)
%%  \citep{key}  ==>>  (Jones et al., 1990)
%%
%% Multiple citations as normal:
%% \citep{key1,key2}         ==>> (Jones et al., 1990; Smith, 1989)
%%                            or  (Jones et al., 1990, 1991)
%%                            or  (Jones et al., 1990a,b)
%% \cite{key} is the equivalent of \citet{key} in author-year mode
%%
%% Full author lists may be forced with \citet* or \citep*, e.g.
%%   \citep*{key}            ==>> (Jones, Baker, and Williams, 1990)
%%
%% Optional notes as:
%%   \citep[chap. 2]{key}    ==>> (Jones et al., 1990, chap. 2)
%%   \citep[e.g.,][]{key}    ==>> (e.g., Jones et al., 1990)
%%   \citep[see][pg. 34]{key}==>> (see Jones et al., 1990, pg. 34)
%%  (Note: in standard LaTeX, only one note is allowed, after the ref.
%%   Here, one note is like the standard, two make pre- and post-notes.)
%%
%%   \citealt{key}          ==>> Jones et al. 1990
%%   \citealt*{key}         ==>> Jones, Baker, and Williams 1990
%%   \citealp{key}          ==>> Jones et al., 1990
%%   \citealp*{key}         ==>> Jones, Baker, and Williams, 1990
%%
%% Additional citation possibilities
%%   \citeauthor{key}       ==>> Jones et al.
%%   \citeauthor*{key}      ==>> Jones, Baker, and Williams
%%   \citeyear{key}         ==>> 1990
%%   \citeyearpar{key}      ==>> (1990)
%%   \citetext{priv. comm.} ==>> (priv. comm.)
%%   \citenum{key}          ==>> 11 [non-superscripted]
%% Note: full author lists depends on whether the bib style supports them;
%%       if not, the abbreviated list is printed even when full requested.
%%
%% For names like della Robbia at the start of a sentence, use
%%   \Citet{dRob98}         ==>> Della Robbia (1998)
%%   \Citep{dRob98}         ==>> (Della Robbia, 1998)
%%   \Citeauthor{dRob98}    ==>> Della Robbia


%% References with bibTeX database:

\bibliographystyle{elsarticle-harv}
\bibliography{geoxiom}

%% Authors are advised to submit their bibtex database files. They are
%% requested to list a bibtex style file in the manuscript if they do
%% not want to use elsarticle-harv.bst.

%% References without bibTeX database:

% \begin{thebibliography}{00}

%% \bibitem must have one of the following forms:
%%   \bibitem[Jones et al.(1990)]{key}...
%%   \bibitem[Jones et al.(1990)Jones, Baker, and Williams]{key}...
%%   \bibitem[Jones et al., 1990]{key}...
%%   \bibitem[\protect\citeauthoryear{Jones, Baker, and Williams}{Jones
%%       et al.}{1990}]{key}...
%%   \bibitem[\protect\citeauthoryear{Jones et al.}{1990}]{key}...
%%   \bibitem[\protect\astroncite{Jones et al.}{1990}]{key}...
%%   \bibitem[\protect\citename{Jones et al., }1990]{key}...
%%   \harvarditem[Jones et al.]{Jones, Baker, and Williams}{1990}{key}...
%%

% \bibitem[ ()]{}

% \end{thebibliography}

\end{document}

%%
%% End of file `elsarticle-template-harv.tex'.
